// 如果后一个字符和前一个字符构成一个合法的字母序列，那么必然两种情况，
// 第一种情况，仅选择当前字符生成字母，那么很明显组合数应当等于前一个字母的组合数
// 第二种情况，选择前一个字符和当前字符共同构成一个字母，那么其组合数应该等于上上一个字符的组合数
// 把这两个组合数加在一起，就得到了当前的组合总数

// 我们分别来讨论一下这几种情况下更新 dp 的方法
// 1. 00 直接返回 0 即可，因为 00 无论如何也无法进行正确解析
// 2. 103 在 03 的情况下和前缀只能产生一种组合
// 3. 126
// 4. 134 在 4 位置上无法构成有效的字符，所以 4 只能单独存在，和前缀只能组成一种组合
// 5. 120 考虑在 0 位置上 20 仅能构成一种组合
// 6. 170 无法解析，直接返回 0 即可

var numDecodings = function (s) {
  if (s[0] == "0") return 0;
  let dp = [1, 1],
    len = s.length;
  for (let i = 1; i < len; i++) {
    if (s[i - 1] != "0") {
      let num = (s[i - 1] + s[i]) | 0;
      if (num >= 1 && num <= 26) {
        dp[i + 1] = s[i] != "0" ? dp[i - 1] + dp[i] : d[i - 1];
      } else if (s[i] != "0") {
        dp[i + 1] = dp[i];
      } else {
        return 0;
      }
    } else if (s[i] != "0") {
      dp[i + 1] = dp[i];
    } else {
      return 0;
    }
  }
  return dp[len];
};

// 当为 1 位数时，形如 X
// 0
// 1. 返回 0
// 2. 非首字母，跳过，此处组合为 0
// 非 0
// 1. 本身为 1 个组合
// 当为 2 位数字时，
// 1X 10 11 12   X 可以是任意数值
// 2X 20 21 22 23 24 25 26    X < 7
// 3X 可以归纳到第一种情况中去，为 1 位数，直接跳过
// 第二种写法
var numDecodings = function (s) {
  if (s[0] == 0) return 0;
  let len = s.length;
  let dp = new Array(len + 1).fill(0);
  dp[0] = dp[1] = 1;
  for (let i = 2; i <= len; i++) {
    if (s[i - 1] != 0) {
      dp[i] += dp[i - 1];
    }
    if (s[i - 2] == 1 || (s[i - 2] == 2 && s[i - 1] <= 6)) {
      dp[i] += dp[i - 2];
    }
  }
  return dp[len];
};
